﻿#define _CRT_SECURE_NO_WARNINGS

#include"Tree.h"


//实现二叉树前序遍历--根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d", root->data);

	//左右两个子树作为根节点继续遍历
	PreOrder(root->left);
	PreOrder(root->right);
}

//实现二叉树中序遍历--左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	
	//不断递归找到左子树最左下角的数据
	InOrder(root->left);
	//找到之后打印数据
	printf("%d ", root->data);
	//继续遍历右子树
	InOrder(root->right);
}

//实现二叉树后序遍历--左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//// 二叉树结点个数 (仍存在*psize中的值没有办法更改的问题)
//void BinaryTreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	++(*psize);
//	BinaryTreeSize(root->left, *psize);
//	BinaryTreeSize(root->right, *psize);
//}
//二叉树求节点个数（完美版）
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// 二叉树叶子结点个数 
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//确认是不是叶子结点
	if (root->left == NULL && root->right == NULL)
	{
		return 0;
	}
	//总叶子结点个数 = 左子树叶子结点个数 + 右子树叶子结点个数
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断结点是不是第k层，如果是则返回1
	if (k == 1)
	{
		return 1;
	}
	//第k层结点个数 = 左子树的第k层结点个数 + 右子树的第k层结点个数
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);

	return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	//先释放左子树和右子树
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

	//最后释放根节点
	free(*root);
	*root == NULL;
}
